#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/04/30
# @Author   :Changshu
# @File     :Exercise25.py
# 25. K 个一组翻转链表

class ListNode:
	def __init__(self,val=0,next=None):
		self.val=val
		self.next=next


def init():
	head = ListNode(0)
	node=head
	node.next=ListNode(1)
	node=node.next
	node.next = ListNode(2)
	node = node.next
	node.next = ListNode(3)
	node = node.next
	node.next = ListNode(4)
	node = node.next
	node.next = ListNode(5)
	node = node.next
	node.next = ListNode(6)
	return head

def printListNode(head:ListNode):
	res=[]
	if not head or not head.next:
		return res
	node=head.next
	while node:
		res.append(str(node.val))
		node=node.next
	return res

# 翻转链表,用三个指针分别指向前，中，后
def reverseListNode(head):
	if not head and not head.next:
		return
	pre=None
	cur=head.next
	while cur:
		tail=cur.next
		# node=cur
		cur.next=pre
		pre=cur
		cur=tail
	# print(cur)
	head.next=pre


def reverseKGroupOfOne(start,end):
	pre=end.next
	cur=start
	while pre!=end:
		tail=cur.next
		cur.next=pre
		pre=cur
		cur=tail
	return end,start


def reverseKGroup(head,k):
	hair=ListNode(-1)
	hair.next=head
	start=hair
	while head:
		end=start
		for i in range(k):
			end=end.next
			if not end:
				return hair.next
		nex=end.next
		head,tail=reverseKGroupOfOne(head,end)
		start.next=head
		tail.next=nex
		start=tail
		head=nex
	return hair.next


def printListNode2(head:ListNode):
	res=[]
	if not head:
		return res
	node=head
	while node:
		res.append(str(node.val))
		node=node.next
	return res

if __name__ == '__main__':
	head=init()
	l=printListNode(head)
	print(' '.join(l))
	# reverseListNode(head)
	# l = printListNode(head)
	# print(' '.join(l))
	node=reverseKGroup(head.next,2)
	l = printListNode2(node)
	print(' '.join(l))

	# n1,n2=reverseKGroupOfOne(head.next,head.next.next.next.next)
	# head.next=n1
	# l = printListNode(head)
	# print(' '.join(l))